

import java.io.*;
import java.util.*;

public class Huffman {
    public static void main(String[] args) {
        String str="i like like like java do you like a java";
        byte[] bytes=str.getBytes();

        byte[] bytes1=setHuffmansize(bytes);
        System.out.println(new String(decode(map, bytes1)));

        huffzip("d:\\ppp.png","d:\\ppp.zip");
        unzip("d:\\ppp.zip","d:\\xxx.png");

    }
    static Map<Byte,String> map=new HashMap<>();

    public static void huffzip(String srcFile,String destFile){
        FileOutputStream fileOutputStream=null;
        ObjectOutputStream objectOutputStream=null;
        FileInputStream fileInputStream=null;
        try {
            fileInputStream=new FileInputStream(srcFile);
            byte[] b=new byte[fileInputStream.available()];
            fileInputStream.read(b);
            byte[] bytes=setHuffmansize(b);
            fileOutputStream=new FileOutputStream(destFile);
            objectOutputStream=new ObjectOutputStream(fileOutputStream);
            objectOutputStream.writeObject(bytes);
            objectOutputStream.writeObject(map);

        } catch (Exception e) {
            System.out.println(e.getMessage());
        }finally {
            try {
                fileOutputStream.close();
                objectOutputStream.close();
                fileInputStream.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }
    public static void unzip(String srcFile,String destFile){
        FileOutputStream fileOutputStream=null;
        FileInputStream fileInputStream=null;
        ObjectInputStream objectInputStream=null;
        try {
            fileInputStream=new FileInputStream(srcFile);
            objectInputStream=new ObjectInputStream(fileInputStream);
            byte[] bytes=(byte[]) objectInputStream.readObject();
            Map<Byte,String> map1=(Map<Byte,String>)objectInputStream.readObject();
            byte[] bytes1=decode(map1,bytes);
            fileOutputStream=new FileOutputStream(destFile);
            fileOutputStream.write(bytes1);

        } catch (Exception e) {
            System.out.println(e.getMessage());
        }finally {
            try {
                fileOutputStream.close();
                objectInputStream.close();
                fileInputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }


    public static byte[] setHuffmansize(byte[] bytes){
        List<Node> list=getNode(bytes);
        Node node=Huffmantree(list);
        Map<Byte,String> Hffmancodes=Hffmancode(node);
        return zip(bytes, Hffmancodes);
    }
    public static byte[] decode(Map<Byte,String> huffmancodes,byte[] bytes){
        StringBuilder stringBuilder=new StringBuilder();
        for (int i = 0; i < bytes.length; i++) {
            byte b=bytes[i];
            boolean flag=(i==bytes.length-1);
            stringBuilder.append(bitToString(!flag,b));
        }

        Map<String,Byte> huffmancodes1=new HashMap<>();
        for (Map.Entry<Byte,String> map:huffmancodes.entrySet()) {
            huffmancodes1.put(map.getValue(),map.getKey());
        }

        List<Byte> list=new ArrayList<>();
        for (int i = 0; i < stringBuilder.length();) {
            int count=1;
            boolean flag=true;
            Byte b = null;
            while (flag){
                flag=true;
                String str=stringBuilder.substring(i,i+count);
                b=huffmancodes1.get(str);
                if (b==null){
                   count++;
                }else {
                   flag=false;
                }
            }
            list.add(b);
            i+=count;
        }

        byte[] bytes1=new byte[list.size()];
        for (int i = 0; i < bytes1.length; i++) {
            bytes1[i]=list.get(i);
        }
        return bytes1;
    }
    public static String bitToString(boolean lag,byte bytes){
       int temp=bytes;
        String str;
       if (lag) {
           temp |= 256;
       }
       str=Integer.toBinaryString(temp);
       if (lag){
           return str.substring(str.length()-8);
       }else {
       return str;
    }
    }
    private static byte[] zip(byte[] bytes,Map<Byte,String> map){
        StringBuilder stringBuilder = new StringBuilder();
        for (byte key:bytes) {
            stringBuilder.append(map.get(key));
        }
        int len=0;
        if (stringBuilder.length()%8==0){
            len=stringBuilder.length()/8;
        } else {
            len=stringBuilder.length()/8+1;
        }
        byte[] bytes1=new byte[len];
        int index=0;
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String str;
            if (i+8>stringBuilder.length()){
                str=stringBuilder.substring(i);
            }else {
                str=stringBuilder.substring(i,i+8);
            }
            bytes1[index]=(byte) Integer.parseInt(str,2);
            index++;
        }
        return bytes1;
    }
    
    
    
    
    
    private static Map<Byte,String> Hffmancode(Node node){
        if (node==null){
            return null;
        }
        HuffmanCode(node.left,"0",new StringBuilder());
        HuffmanCode(node.right,"1",new StringBuilder());
        return map;
    }
    
    
    public static void HuffmanCode(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node!=null){
            if (node.date!=null){
                map.put(node.date,stringBuilder1.toString());
            }else{
                HuffmanCode(node.left,"0",stringBuilder1);
                HuffmanCode(node.right,"1",stringBuilder1);
            }
        }
       
    }
    public static List<Node> getNode(byte[] bytes){
        ArrayList<Node> list=new ArrayList<>();
        Map<Byte,Integer> map=new HashMap<>();
        for (byte b:bytes) {
            Integer count=map.get(b);
            if (count==null){
                map.put(b,1);
            }else {
                map.put(b,count+1);
            }
        }
        for (Map.Entry<Byte,Integer> entry:map.entrySet()) {
            list.add(new Node( entry.getKey(),entry.getValue()));
        }
        return list;
    }
    public static Node Huffmantree(List<Node> list){
        while (list.size()>1){
            Collections.sort(list);
            Node left=list.get(0);
            Node right=list.get(1);
            Node present=new Node(null,left.values+ right.values);
            present.left=left;
            present.right=right;
            list.remove(left);
            list.remove(right);
            list.add(present);
        }
        return list.get(0);
    }
    public static void hfm(Node node){
        if (node!=null){
            node.por();
        }else {
            System.out.println("null");
        }
    }

}

class Node implements Comparable<Node>{
    public Node left;
    public Node right;
    public int values;
    public Byte date;

    public Node(Byte date,int values) {
        this.values = values;
        this.date = date;
    }

    @Override
    public String toString() {
        return "Node{" +
                "values=" + values +
                ", date=" + date +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.values-o.values;
    }
    public void por(){
        System.out.println(this);
        if (this.left!=null){
            this.left.por();
        }
        if (this.right!=null){
            this.right.por();
        }
    }

}